//
// Created by Semir on 2020/5/16.
//

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


void ConnectTreeNode(TreeNode* pRoot, TreeNode* pLeft, TreeNode* pRight) {
    if (pRoot == nullptr) {
        return;
    }
    pRoot->left = pLeft;
    pRoot->right = pRight;
}

TreeNode* BuildTree1() {
    auto* node1 = new TreeNode(10);
    auto* node2 = new TreeNode(5);
    auto* node3 = new TreeNode(12);
    auto* node4 = new TreeNode(4);
    auto* node5 = new TreeNode(7);

    ConnectTreeNode(node1, node2, node3);
    ConnectTreeNode(node2, node4, node5);

    return node1;
}

void FindPath(TreeNode* root, int expectNumber, int val, vector<vector<int>>& res, vector<int> path) {
    if (root == nullptr && expectNumber == val) {
        res.emplace_back(path);
        return;
    }
    if (root == nullptr || expectNumber <= val) {
        return;
    }
    val += root->val;
    path.emplace_back(root->val);
    if (root->left && root->right) {
        FindPath(root->left, expectNumber, val, res, path);
        FindPath(root->right, expectNumber, val, res, path);
    } else if (root->right) {
        FindPath(root->right, expectNumber, val, res, path);
    } else {
        FindPath(root->left, expectNumber, val, res, path);
    }
}

vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
    vector<vector<int>> res;
    if (root == nullptr) {
        return res;
    }
    vector<int> path;
    FindPath(root, expectNumber, 0, res, path);
    return res;
}

int main() {
    TreeNode* root = BuildTree1();
    vector<vector<int>> res = FindPath(root, 22);
    cout << res.size() << endl;
    return 0;
}